import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Test41_1 {
    private static class Heap<T>{
        private List<T> data;//堆中存放元素的集合
        //比较器
        private Comparator<T> cmp;
        //构造器
        public Heap(Comparator<T> cmp){
            this.cmp = cmp;
            this.data = new ArrayList<>(64);
        }

        //向上调整，
        public void shiftup(int index){
            //检查是否正确
            if (index < 0 || index  > data.size()) throw new IllegalArgumentException("invalid");
            //获取开始调整的元素
            T temp= data.get(index);
            while(index > 0) { //如果没有到达根元素
                int parentindex = (index-1)/2;//找到父节点
                T parent = data.get(parentindex);
                if (cmp.compare(temp,parent) > 0){
                    //父节点小于temp，上移
                    //如果是最小堆：父节点大于temp，上移，看如何定义比较器
                    //将父节点放入当前位置，index只想父节点的index
                    data.set(index,parent);
                    index = parentindex;
                }else break; //结束找到位置
            }
            data.set(index,temp);//找到最后的位置，将temp放入
        }

        //向下调整
        public void siftDown(int index){
            if (index < 0|| index > data.size()) throw new IllegalArgumentException("invalid");
            T temp = data.get(index);
            int leftindex = index*2+1;//当前节点的左子节点
            while(leftindex < data.size()){
                T maxChild  = data.get(leftindex);//获取左子节点的对象，假设当前左子节点为最大的
                int maxindex = leftindex;
                //获取右子节点
                int rightindex = leftindex+1;
                if (rightindex < data.size()){
                    T rigthChild = data.get(rightindex);
                    if(cmp.compare(maxChild,rigthChild) < 0){
                        maxChild = rigthChild;
                        maxindex = rightindex;
                    }
                }
                //如果最大子节点比父节点大，则需要下移
                if (cmp.compare(maxChild,temp) > 0){
                    data.set(index,maxChild);
                    index = maxindex;
                    leftindex = index *2+1;
                }
                else break;
            }
            data.set(index,temp);
        }

        public void add(T t){
            data.add(t);
            shiftup(data.size()-1);
        }

        //删除堆定元素
        public T delete(){
            if (data.isEmpty()) throw new IllegalArgumentException("isEmpty");
            T first = data.get(0);
            T temp = data.remove(data.size()-1);
            // 删除元素后，如果堆为空的情况，说明删除的元素也是堆顶元素
            if (data.size() == 0) return temp;
            data.set(0,temp);
            siftDown(0);
            return first;
        }

        //获取堆定元素
        public T getTop() {
            // 如果堆已经为空，就抛出异常
            if (data.isEmpty()) {
                throw new RuntimeException("The heap is empty.");
            }
            return data.get(0);
        }
        /**
         * 获取堆的大小
         *
         * @return 堆的大小
         */
        public int size() {
            return data.size();
        }

        /**
         * 判断堆是否为空
         *
         * @return 堆是否为空
         */
        public boolean isEmpty() {
            return data.isEmpty();
        }

        /**
         * 清空堆
         */
        public void clear() {
            data.clear();
        }

        /**
         * 获取堆中所有的数据
         *
         * @return 堆中所在的数据
         */
        public List<T> getData() {
            return data;
        }

    }
    /**
     * 升序比较器
     */
    private static class IncComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 - o2;
        }
    }

    /**
     * 降序比较器
     */
    private static class DescComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    }

    private static class DynamicArray{
        private Heap<Integer> max; //大顶堆
        private Heap<Integer> min; //小顶堆

        public DynamicArray(){
            max = new Heap<>(new IncComparator());
            min = new Heap<>(new DescComparator());
        }

        public void insert(Integer num){
            // 已经有偶数个数据了（可能没有数据）
            // 数据总数是偶数个时把新数据插入到小堆中
            if ((min.size() + max.size()) % 2 == 0){
                if (max.size() > 0 &&num < max.getTop()){
                    //如果插入的数据比大堆中也是就是左堆小的话，先插入大堆
                    max.add(num);
                    //删除堆定元素，也就是大堆中最大的元素
                    num = max.delete();
                }
                //把num加入小堆,现在小堆的堆顶为num
                min.add(num);
            }else{
                // 数据总数是奇数个时把新数据插入到大堆中
                if (min.size() > 0 && num > min.getTop()){
                    // 将num加入的小堆中去
                    min.add(num);
                    // 删除堆顶元素，小堆中的最小元素
                    num = min.delete();
                }
                max.add(num);
            }
        }
        public double getMid(){
            int size = max.size() + min.size();
            if (size == 0) {
                throw new RuntimeException("No numbers are available");
            }
            if ((size & 1) == 1) { //奇数
                return min.getTop();
            } else {
                return (max.getTop() + min.getTop()) / 2.0;
            }
        }
    }

    public static void main(String[] args) {
        // 2 3 4 5 5 7 10 10
        DynamicArray array = new DynamicArray();
        array.insert(5);
        System.out.println(array.getMid());
        array.insert(2);
        System.out.println(array.getMid());
        array.insert(3);
        System.out.println(array.getMid());
        array.insert(4);
        System.out.println(array.getMid());
        array.insert(10);
        System.out.println(array.getMid());
        array.insert(5);
        System.out.println(array.getMid());
        array.insert(7);
        System.out.println(array.getMid());
        array.insert(10);
        System.out.println(array.getMid());
    }
}
